home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / linklist / source.lha / list.c < prev    next >
C/C++ Source or Header  |  1993-08-08  |  41KB  |  1,849 lines
  1. /*
  2. **    Anita Eijs    TNO-BOUW, BouwInformatica    May 1989
  3. **
  4. **    Generic Linked List Package
  5. **
  6. **    Updates:
  7. **    900402    New routine:
  8. **            lIndxNode    Get node by index.
  9. **
  10. **    900925    New routine:
  11. **            lError    print error message in lERROR_FILE
  12. **
  13. **    901129    New routines:
  14. **            lDump    Dump a linked list to a file.
  15. **            lUndump    Undump a linked list from a file.
  16. **
  17. **    910301    'Mac'ed by Vinnie:
  18. **            ListPtr = ListyPtr
  19. **            Byte = byte
  20. **            includes
  21. **            typecasts
  22. **
  23. **    910316    New routine:
  24. **            lFlagNode    Get node by flag.
  25. **
  26. **    ***** Version 0.7, March 1992 *****
  27. **
  28. **    930401    Several updates by Anita and Shane.
  29. **        Some functions renamed:
  30. **            lIndxNode --> lGetIndxNode
  31. **            lFlagNode --> lFndFlagNode
  32. **        New routines:
  33. **            lSort        Sort a linked list.
  34. **            lInfoIndxNode    Get information about node by index.
  35. **            lDelIndxNode    Delete node by index.
  36. **            lUpdIndxNode    Update node by index.
  37. **        Parameter where added to lFndFlagNode to find several nodes
  38. **        matching the requested flag.
  39. **        Defines are made more specific; FIRST is renamed in lFIRST, etc.
  40. **
  41. **    ***** Version 0.8, May 1993 *****
  42. */
  43.  
  44. #ifdef MAC
  45. #define    MAC_OR_VAXC
  46. #endif
  47. #ifdef VAXC
  48. #define    MAC_OR_VAXC
  49. #define    MSDOS_OR_VAXC
  50. #endif
  51. #ifdef MSDOS
  52. #define    MSDOS_OR_VAXC
  53. #endif
  54.  
  55. #ifdef MAC
  56. #include    <unix.h>    /* open, creat, write, read, close */
  57. #include    <stddef.h>    /* sizeof */
  58. #endif
  59.  
  60. #ifdef MAC_OR_VAXC
  61. #include    <stdlib.h>
  62. #else
  63. #include    <malloc.h>
  64. #endif
  65.  
  66. #ifdef MSDOS
  67. #include    <io.h>    /* open, creat, write, read, close */
  68. #endif
  69.  
  70. #include    <stdio.h>
  71. #include    "list.h"
  72.  
  73. /* -------------------------------------------------------------------------- */
  74.  
  75. #ifndef NULL
  76. #define    NULL    0
  77. #endif
  78.  
  79. #undef    FREE
  80. #define FREE(VAR) if (VAR != NULL) free((char *)VAR);
  81. #undef    MALLOC
  82. #define MALLOC(VAR, TYPE) \
  83.     if ((VAR = (TYPE *)malloc(sizeof(TYPE))) == NULL) { \
  84.         fprintf(stderr, "No more memory for malloc().\n"); \
  85.     }
  86. #undef    CALLOC
  87. #define CALLOC(VAR, TYPE, NR) \
  88.     if ((VAR = (TYPE *)calloc(NR, sizeof(TYPE))) == NULL) {\
  89.         fprintf(stderr, "No more memory for calloc().\n"); \
  90.     }
  91.  
  92. #undef    BYTE_COPY
  93. #define BYTE_COPY(FROM, TO, SIZE) \
  94.     { \
  95.         register Byte    *frm = FROM, \
  96.                 *to = TO; \
  97.         int        i = SIZE; \
  98.         while (i--) *to++ = *frm++; \
  99.     }
  100.  
  101. #define    BIN_WRITE    1    /* necessary for binary file access */
  102. #define    BIN_READ    0
  103. #define    PMODE        0666
  104.  
  105. /* -------------------------------------------------------------------------- */
  106.  
  107. #ifndef ANSI
  108. typedef    int        (*Func)();
  109. typedef    unsigned char    Byte;
  110. #endif
  111.  
  112. typedef struct lnode {
  113.     Byte        *data;    /* data of user */
  114.     int        size;    /* size (number of bytes) of data */
  115.     int        flag;    /* user information flag */
  116.     struct lnode    *prv;    /* previous node */
  117.     struct lnode    *nxt;    /* next node */
  118. } ListNode, *NodePtr;
  119.  
  120. typedef struct listhdr {
  121.     int        id;        /* identifier of linked list */
  122.     int        sd;        /* singly or doubly linked */
  123.     int        cc;        /* chain or circular list */
  124.     int        n;        /* number of nodes */
  125.     NodePtr        first;        /* address of first node */
  126.     NodePtr        current;    /* address of current node */
  127.     NodePtr        last;        /* address of last node */
  128.     struct listhdr    *nxt;        /* next linked list */
  129. } ListHdr, *ListPtr;
  130.  
  131. typedef struct header {    /* general info of linked list for dump file */
  132.     int    sd;
  133.     int    cc;
  134.     int    n;
  135. } Header;
  136.  
  137. typedef struct info {    /* general info of node for dump file */
  138.     int    size;
  139.     int    flag;
  140. } Info;
  141.  
  142. /* -------------------------------------------------------------------------- */
  143.  
  144. #ifdef ANSI
  145. static ListPtr    getAddress(int id);
  146. static void    delNodes(NodePtr node, int n);
  147. static void    delListInfo(ListPtr list);
  148. static void    lError(char *str, int code, int int1, int int2, char *str1);
  149. static int    setWhchNode(int id, int which, char *fname);
  150. static int    setIndxNode(int id, int index, char *fname);
  151. static int    partition(NodePtr *array, int order, Func func, int lb, int ub,
  152.             int *pj);
  153. static int    stack_empty(int id);
  154. static int    intInSet(int intgr, int *set, int set_n);
  155. #else
  156. static ListPtr    getAddress();
  157. static void    delNodes();
  158. static void    delListInfo();
  159. static void    lError();
  160. static int    setWhchNode();
  161. static int    setIndxNode();
  162. static int    partition();
  163. static int    stack_empty();
  164. static int    intInSet();
  165. #endif
  166.  
  167. /* -------------------------------------------------------------------------- */
  168.  
  169. static ListHdr    firstlist = { 1, 0, 0, 0, NULL, NULL, NULL, NULL };
  170. static ListPtr    ld = &firstlist;
  171. static int    idMax = 2;
  172.  
  173. /* -------------------------------------------------------------------------- */
  174.  
  175. /*******************************************************************************
  176. ** Define a new linked list and create info about it.
  177. **
  178. ** Parameters:
  179. **    In    int    sd    singly or doubly linked
  180. **                (lSINGLY, lDOUBLY)
  181. **    In    int    cc    chain or circular linked
  182. **                (lCHAIN, lCIRCULAR)
  183. **
  184. ** Return on success:
  185. **    identifier of linked list
  186. ** Return on error:
  187. **    lWRONG_SD, lWRONG_CC
  188. */
  189. #ifdef ANSI
  190. int
  191. lDef(int sd, int cc)
  192. #else
  193. int
  194. lDef(sd, cc)
  195. int    sd, cc;
  196. #endif
  197. {
  198.     ListPtr        list, new;
  199.     static int    set1[] = { lSINGLY, lDOUBLY },
  200.             set2[] = { lCHAIN, lCIRCULAR };
  201.  
  202.         /* check parameters */
  203.     if (intInSet(sd, set1, 2) != 0) {
  204.         lError("lDef", lWRONG_SD, sd, 0, NULL);
  205.         return(lWRONG_SD);
  206.     }
  207.     if (intInSet(cc, set2, 2) != 0) {
  208.         lError("lDef", lWRONG_CC, cc, 0, NULL);
  209.         return(lWRONG_CC);
  210.     }
  211.  
  212.     list = ld;
  213.     while (list->nxt != NULL && list->sd != 0)
  214.         list = list->nxt;
  215.     if (list->sd != 0) {    /* new list */
  216.         MALLOC(new, ListHdr);
  217.         new->id = idMax++;
  218.         new->sd = sd;
  219.         new->cc = cc;
  220.         new->n = 0;
  221.         new->first = new->current = new->last = NULL;
  222.         new->nxt = NULL;
  223.         list->nxt = new;
  224.         return(new->id);
  225.     } else {        /* new list on existing place */
  226.         list->sd = sd;
  227.         list->cc = cc;
  228.         return(list->id);
  229.     }
  230. }
  231.  
  232. /*******************************************************************************
  233. ** Get info of linked list.
  234. **
  235. ** Parameters:
  236. **    In    int    id    identifier of linked list
  237. **    Out    int    *sd    singly or doubly linked
  238. **                (lSINGLY, lDOUBLY)
  239. **    Out    int    *cc    chain or cicular linked
  240. **                (lCHAIN, lCIRCULAR)
  241. **    Out    int    *n    number of nodes
  242. **
  243. ** Return on success:
  244. **    lSUCCESS
  245. ** Return on error:
  246. **    lUNKNOWN_ID
  247. */
  248. #ifdef ANSI
  249. int
  250. lInfo(int id, int *sd, int *cc, int *n)
  251. #else
  252. int
  253. lInfo(id, sd, cc, n)
  254. int    id, *sd, *cc, *n;
  255. #endif
  256. {
  257.     ListPtr    list;
  258.  
  259.         /* check parameters */
  260.     if ((list = getAddress(id)) == NULL) {
  261.         lError("lInfo", lUNKNOWN_ID, id, 0, NULL);
  262.         return(lUNKNOWN_ID);
  263.     }
  264.  
  265.         /* copy information */
  266.     *sd = list->sd;
  267.     *cc = list->cc;
  268.     *n = list->n;
  269.  
  270.     return(lSUCCESS);
  271. }
  272.  
  273. /*******************************************************************************
  274. ** Sort a linked list.
  275. **
  276. ** Parameters:
  277. **    In    int    id    identifier of linked list
  278. **    In    int    order    sorting order
  279. **                (lDESCENDING, lASCENDING)
  280. **    In    int    theory    sorting theory
  281. **                (lBUBBLE, lHEAP, lINSERT, lQUICK, lSELECTION)
  282. **    In    Func    func    number of nodes
  283. **
  284. ** Return on success:
  285. **    lSUCCESS
  286. ** Return on error:
  287. **    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_ORDER, lWRONG_THEORY
  288. */
  289. #ifdef ANSI
  290. int lSort(int id, int order, int theory, Func func)
  291. #else
  292. int
  293. lSort(id, order, theory, func)
  294. int    id, order, theory;
  295. Func    func;
  296. #endif
  297. {
  298.     int        node_n, i, s, f, k, where, j, cmp;
  299.     ListPtr        list;
  300.     NodePtr        temp, temp2, *array;
  301.     static int    set1[] = { lASCENDING, lDESCENDING },
  302.             set2[] = { lBUBBLE, lHEAP, lINSERT, lQUICK,
  303.                 lSELECTION };
  304.  
  305.         /* check parameters */
  306.     if ((list = getAddress(id)) == NULL) {
  307.         lError("lSort", lUNKNOWN_ID, id, 0, NULL);
  308.         return(lUNKNOWN_ID);
  309.     }
  310.     if (list->n == 0) {
  311.         lError("lSort", lEMPTY_LIST, id, 0, NULL);
  312.         return(lEMPTY_LIST);
  313.     }
  314.     if (intInSet(order, set1, 2) != 0) {
  315.         lError("lSort", lWRONG_ORDER, id, 0, NULL);
  316.         return(lWRONG_ORDER);
  317.     }
  318.     if (intInSet(theory, set2, 5) != 0) {
  319.         lError("lSort", lWRONG_THEORY, id, 0, NULL);
  320.         return(lWRONG_THEORY);
  321.     }
  322.  
  323.     node_n = list->n;
  324.         /* allocate 1 extra so I can nave a null in it */
  325.     CALLOC(array, NodePtr, node_n+1);
  326.  
  327.     list->current = list->first;
  328.     for (i=0; i<node_n && list->current != NULL ; i++) {
  329.         array[i] = list->current;
  330.         list->current = (list->current)->nxt;
  331.     }
  332.     array[node_n] = NULL;
  333.  
  334.     switch (theory) {
  335.     case lBUBBLE: {
  336.         int    switched = 1;
  337.  
  338.         for (i=0; i < node_n-1 && switched == 1; i++) {
  339.             switched = 0;
  340.             for (j=0; j < node_n-i-1; j++) {
  341.                 cmp = (*func)(array[j]->data, array[j+1]->data);
  342.                 if ((order == lASCENDING && cmp == l2LT1)
  343.                  || (order == lDESCENDING && cmp == l1LT2)) {
  344.                     temp = array[j];
  345.                     array[j] = array[j+1];
  346.                     array[j+1] = temp;
  347.  
  348.                     switched = 1;
  349.                 }
  350.             }
  351.         }
  352.         break;
  353.     } /* end of lBUBBLE */
  354.     case lHEAP:
  355.         for (i=1; i<node_n; i++) {
  356.             temp = array[i];
  357.  
  358.             s = i;
  359.             f = (s-1)/2;
  360.             cmp = (*func)(array[f]->data, temp->data);
  361.             while (s > 0 && ((order == lASCENDING && cmp == l1LT2)
  362.              || (order == lDESCENDING && cmp == l2LT1))) {
  363.                 array[s] = array[f];
  364.                 s = f;
  365.                 f = (s-1)/2;
  366.                 cmp = (*func)(array[f]->data, temp->data);
  367.             }
  368.  
  369.             array[s] = temp;
  370.         }
  371.         for (i=node_n-1; i>0; i--) {
  372.             temp = array[i];
  373.             array[i] = array[0];
  374.             f = 0;
  375.  
  376.             if (i == 1)
  377.                 s = -1;
  378.             else
  379.                 s = 1;
  380.             cmp = (*func)(array[2]->data, array[1]->data);
  381.             if (i > 2 && ((order == lASCENDING && cmp == l2LT1)
  382.              || (order == lDESCENDING && cmp == l1LT2)))
  383.                 s = 2;
  384.  
  385.             if (s >= 0)
  386.                 cmp = (*func)(temp->data, array[s]->data);
  387.             while (s >= 0 && ((order == lASCENDING && cmp == l1LT2)
  388.              || (order == lDESCENDING && cmp == l2LT1))) {
  389.                 array[f] = array[s];
  390.                 f = s;
  391.  
  392.                 s = 2*f+1;
  393.                 if (s+1 <= i-1) {
  394.                     cmp = (*func)(array[s]->data,
  395.                         array[s+1]->data);
  396.                     if (cmp < 0)
  397.                         s = s+1;
  398.                 }
  399.                 if (s > i-1)
  400.                     s = -1;
  401.                 if (s >= 0)
  402.                     cmp = (*func)(temp->data,
  403.                         array[s]->data);
  404.             }
  405.             array[f] = temp;
  406.         }
  407.         break;
  408.     case lINSERT:
  409.         for (i=1; i<node_n; i++) {
  410.             temp = array[i];
  411.             cmp = (*func)(temp->data, array[i-1]->data);
  412.             for (j=i-1; j>=0
  413.              && ((order == lASCENDING && cmp == l1LT2)
  414.              || (order == lDESCENDING && cmp == l2LT1)); j--) {
  415.                 temp2 = array[j];
  416.                 array[j] = array[j+1];
  417.                 array[j+1] = temp2;
  418.                 if (j > 0)
  419.                     cmp = (*func)(temp->data,
  420.                         array[j-1]->data);
  421.             }
  422.         }
  423.         break;
  424.     case lQUICK: {
  425.         struct bndtype {
  426.             int lb;
  427.             int ub;
  428.         }        newbnds;
  429.         int        newbndsSz = sizeof(struct bndtype),
  430.                 stack = lDef(lDOUBLY, lCHAIN);
  431.  
  432.         newbnds.lb = 0;
  433.         newbnds.ub = node_n-1;
  434.             /* basicly a push */
  435.         lInsNode(stack, lLAST, &newbnds, newbndsSz, 0);
  436.  
  437.             /* repeat as long as there are any unsorted subarrays
  438.             ** on the stack */
  439.         while (!stack_empty(stack)) {
  440.                 /* a pop */
  441.             lGetNode(stack, lCURRENT, &newbnds, newbndsSz);
  442.             lDelNode(stack, lCURRENT);
  443.             while (newbnds.ub > newbnds.lb) {
  444.                     /* process next sub array */
  445.                 partition(array, order, (*func), newbnds.lb,
  446.                     newbnds.ub, &j);
  447.                     /* stack the larger subarray */
  448.                 if (j-newbnds.lb > newbnds.ub-j) {
  449.                         /* stack lower subarray */
  450.                     i = newbnds.ub;
  451.                     newbnds.ub = j-1;
  452.                         /* basicly a push */
  453.                     lInsNode(stack, lLAST, &newbnds,
  454.                         newbndsSz, 0);
  455.                         /* process upper subarray */
  456.                     newbnds.lb = j+1;
  457.                     newbnds.ub = i;
  458.                 } else {
  459.                         /* stack upper subarray */
  460.                     i = newbnds.lb;
  461.                     newbnds.lb = j+1;
  462.                         /* basicly a push */
  463.                     lInsNode(stack, lLAST, &newbnds,
  464.                         newbndsSz, 0);
  465.                         /* process lower subarray */
  466.                     newbnds.lb = i;
  467.                     newbnds.ub = j-1;
  468.                 }
  469.             }
  470.         }
  471.         lDel(stack);
  472.         break;
  473.     } /* end of lQUICK */
  474.     case lSELECTION: {
  475.         int    indx;
  476.  
  477.         for (i=node_n-1; i>0 ; i--) {
  478.             temp = array[0];
  479.             indx = 0;
  480.  
  481.             for (j=1; j<=i; j++) {
  482.                 cmp = (*func)(array[j]->data, temp->data);
  483.                 if ((order == lASCENDING && cmp == l2LT1)
  484.                  || (order == lDESCENDING && cmp == l1LT2)) {
  485.                     temp = array[j];
  486.                     indx = j;
  487.                 }
  488.             }
  489.             array[indx] = array[i];
  490.             array[i] = temp;
  491.         }
  492.         break;
  493.     } /* end of lSELECTION */
  494.     } /* end of switch */
  495.  
  496.         /* init list to start and reset it */
  497.     list->first = array[0];
  498.     list->last = array[node_n-1];
  499.  
  500.     list->current = list->first;
  501.     for (k=0; k<node_n; k++) {
  502.         if (k == 0)
  503.             where = lFIRST;
  504.         else if (k == node_n)
  505.             where = lLAST;
  506.         else
  507.             where = lNEXT;
  508.  
  509.         switch (where) {
  510.         case lFIRST:
  511.             if (list->cc == lCIRCULAR)
  512.                 (list->first)->prv = (list->last);
  513.  
  514.             if (list->sd == lDOUBLY)
  515.                 array[k]->prv = NULL;
  516.  
  517.             array[k]->nxt = array[k+1];
  518.             break;
  519.  
  520.         case lNEXT:
  521.             if (list->sd == lDOUBLY)
  522.                 (list->first)->prv = array[k-1];
  523.  
  524.             array[k]->nxt = array[k+1];
  525.             break;
  526.  
  527.         case lLAST:
  528.             if (list->sd == lDOUBLY)
  529.                 array[k]->prv = array[k-1];
  530.  
  531.             if (list->cc == lCIRCULAR)
  532.                 array[k]->nxt = list->first;
  533.             else
  534.                 array[k]->nxt = NULL;
  535.             break;
  536.         }
  537.     }
  538.     FREE(array);
  539.  
  540.     return(lSUCCESS);
  541. }
  542.  
  543. /*******************************************************************************
  544. ** Dump a linked list to a file.
  545. **
  546. ** Parameters:
  547. **    In    int    id    identifier of linked list
  548. **    In    char    *file    name of linked list dump file
  549. **
  550. ** Return on success:
  551. **    lSUCCESS
  552. ** Return on error:
  553. **    lUNKNOWN_ID, lOPEN_ERROR
  554. **
  555. ** File structure:
  556. **    <header> { <info> <data> }
  557. **    header.n    number of <info>-<data>-combinations (nodes)
  558. **    info.size    size of <data>
  559. */
  560. #ifdef ANSI
  561. int
  562. lDump(int id, char *file)
  563. #else
  564. int
  565. lDump(id, file)
  566. int    id;
  567. char    *file;
  568. #endif
  569. {
  570. #ifndef MSDOS
  571.     int    open(), creat(), write(), close();
  572. #endif
  573.  
  574.     int    fdDump, i;
  575.     ListPtr    list;
  576.     NodePtr    node;
  577.     Info    info;
  578.     Header    header;
  579.  
  580.         /* check parameters */
  581.     if ((list = getAddress(id)) == NULL) {
  582.         lError("lDump", lUNKNOWN_ID, id, 0, NULL);
  583.         return(lUNKNOWN_ID);
  584.     }
  585.  
  586.     fdDump = open(file, BIN_WRITE);
  587.     if (fdDump == -1) {
  588.         fdDump = creat(file, PMODE);
  589.         if (fdDump == -1) {
  590.             lError("lDump", lOPEN_ERROR, 0, 0, file);
  591.             return(lOPEN_ERROR);
  592.         }
  593.     }
  594.  
  595.     header.sd = list->sd;
  596.     header.cc = list->cc;
  597.     header.n = list->n;
  598.     write(fdDump, (char *) &header, sizeof(Header));
  599.  
  600.     node = list->first;
  601.     for (i=0; i<header.n; i++) {
  602.         info.size = node->size;
  603.         info.flag = node->flag;
  604.         write(fdDump, (char *) &info, sizeof(Info));
  605.         write(fdDump, (char *) node->data, node->size);
  606.         node = node->nxt;
  607.     }
  608.  
  609.     close(fdDump);
  610.  
  611.     return(lSUCCESS);
  612. }
  613.  
  614. /*******************************************************************************
  615. ** Undump a linked list from a file.
  616. **
  617. ** Parameters:
  618. **    In    char    *file    name of linked list dump file
  619. **
  620. ** Return on success:
  621. **    lSUCCESS
  622. ** Return on error:
  623. **    lOPEN_ERROR
  624. */
  625. #ifdef ANSI
  626. int
  627. lUndump(char *file)
  628. #else
  629. int
  630. lUndump(file)
  631. char    *file;
  632. #endif
  633. {
  634. #ifndef MSDOS
  635.     int    open(), read(), close();
  636. #endif
  637.  
  638.     int    fdDump, i, id;
  639.     Info    info;
  640.     Header    header;
  641.     Byte    *data;
  642.  
  643.         /* check parameters */
  644.     fdDump = open(file, BIN_READ);
  645.     if (fdDump == -1) {
  646.         lError("lDump", lOPEN_ERROR, 0, 0, file);
  647.         return(lOPEN_ERROR);
  648.     }
  649.  
  650.     read(fdDump, (char *) &header, sizeof(Header));
  651.     id = lDef(header.sd, header.cc);
  652.  
  653.     for (i=0; i<header.n; i++) {
  654.         read(fdDump, (char *) &info, sizeof(Info));
  655.         CALLOC(data, Byte, info.size);
  656.         read(fdDump, (char *) data, info.size);
  657.         lInsNode(id, lLAST, data, info.size, info.flag);
  658.         FREE(data);
  659.     }
  660.  
  661.     close(fdDump);
  662.  
  663.     return(id);
  664. }
  665.  
  666. /*******************************************************************************
  667. ** Delete a linked list and clear info about it.
  668. **
  669. ** Parameters:
  670. **    In    int    id    identifier of linked list
  671. **
  672. ** Return on success:
  673. **    lSUCCESS
  674. ** Return on error:
  675. **    lUNKNOWN_ID
  676. */
  677. #ifdef ANSI
  678. int
  679. lDel(int id)
  680. #else
  681. int
  682. lDel(id)
  683. int    id;
  684. #endif
  685. {
  686.     ListPtr    list;
  687.  
  688.         /* check parameters */
  689.     if ((list = getAddress(id)) == NULL) {
  690.         lError("lDel", lUNKNOWN_ID, id, 0, NULL);
  691.         return(lUNKNOWN_ID);
  692.     }
  693.  
  694.         /* delete all nodes */
  695.     delNodes(list->first, list->n);
  696.         /* reset info as deleted linked list */
  697.     list->sd = list->cc = list->n = 0;
  698.     list->first = list->current = list->last = NULL;
  699.  
  700.     return(lSUCCESS);
  701. }
  702.  
  703. /*******************************************************************************
  704. ** Delete all linked list and all info about those lists.
  705. **
  706. ** No parameters.
  707. **
  708. ** Return on success:
  709. **    lSUCCESS
  710. ** Return on error:
  711. **    lNO_LIST
  712. */
  713. #ifdef ANSI
  714. int
  715. lDelAll(void)
  716. #else
  717. int
  718. lDelAll()
  719. #endif
  720. {
  721.     ListPtr    list, nxt;
  722.  
  723.     if (ld == NULL) {
  724.         lError("lDelAll", lNO_LIST, 0, 0, NULL);
  725.         return(lNO_LIST);
  726.     }
  727.  
  728.     list = ld;
  729.     while (list != NULL) {
  730.         nxt = list->nxt;
  731.         if (list->sd != 0 && list->cc != 0)
  732.             lDel(list->id);    /* delete when not already deleted */
  733.         list = nxt;
  734.     }
  735.     delListInfo(ld->nxt);
  736.         /* save info of initial list */
  737.     firstlist.id = 1;
  738.     firstlist.sd = firstlist.cc = firstlist.n = 0;
  739.     firstlist.first = firstlist.current = firstlist.last = NULL;
  740.     firstlist.nxt = NULL;
  741.     ld = &firstlist;
  742.     idMax = 2;
  743.  
  744.     return(lSUCCESS);
  745. }
  746.  
  747. /*******************************************************************************
  748. ** Insert a node in linked list.
  749. **
  750. ** Parameters:
  751. **    In    int    id    identifier of linked list
  752. **    In    int    where    place where node must be inserted
  753. **                (lFIRST, lBEFORE, lAFTER, lLAST)
  754. **    In    Byte    *data    data of node
  755. **    In    int    size    size of data
  756. **    In    int    flag    user information flag
  757. **
  758. ** Return on success:
  759. **    lSUCCESS
  760. ** Return on error:
  761. **    lUNKNOWN_ID, lWRONG_WHERE
  762. */
  763. #ifdef ANSI
  764. int
  765. lInsNode(int id, int where, Byte *data, int size, int flag)
  766. #else
  767. int
  768. lInsNode(id, where, data, size, flag)
  769. int    id, where, size, flag;
  770. Byte    *data;
  771. #endif
  772. {
  773.     ListPtr        list;
  774.     NodePtr        node, new;
  775.     static int    set[] = { lFIRST, lBEFORE, lAFTER, lLAST };
  776.  
  777.         /* check parameters */
  778.     if ((list = getAddress(id)) == NULL) {
  779.         lError("lInsNode", lUNKNOWN_ID, id, 0, NULL);
  780.         return(lUNKNOWN_ID);
  781.     }
  782.     if (intInSet(where, set, 4) != 0) {
  783.         lError("lInsNode", lWRONG_WHERE, where, 0, NULL);
  784.         return(lWRONG_WHERE);
  785.     }
  786.  
  787.         /* create new node */
  788.     MALLOC(new, ListNode);
  789.     CALLOC(new->data, Byte, size);
  790.     BYTE_COPY(data, new->data, size);
  791.     new->size = size;
  792.     new->flag = flag;
  793.  
  794.         /* specific insert cases */
  795.     if (list->first == NULL)
  796.         where = lONE_NODE;    /* first node in list */
  797.     else if (list->current == list->first && where == lBEFORE)
  798.         where = lFIRST;        /* before first is like insert first */
  799.     else if (list->current == list->last && where == lAFTER)
  800.         where = lLAST;        /* after last is like insert last */
  801.  
  802.     switch (where) {
  803.     case lONE_NODE:
  804.         if (list->cc == lCHAIN)
  805.             new->prv = new->nxt = NULL;
  806.         else {
  807.             if (list->sd == lDOUBLY)
  808.                 new->prv = new;
  809.             else
  810.                 new->prv = NULL;
  811.             new->nxt = new;
  812.         }
  813.         list->first = list->last = new;
  814.         break;
  815.     case lFIRST:
  816.         new->prv = (list->first)->prv;
  817.         new->nxt = list->first;
  818.         if (list->cc == lCIRCULAR)
  819.             (list->last)->nxt = new;
  820.         else
  821.             (list->last)->nxt = NULL;
  822.         if (list->sd == lDOUBLY)
  823.             (list->first)->prv = new;
  824.         list->first = new;
  825.         break;
  826.     case lBEFORE:
  827.         new->prv = (list->current)->prv;    /* == NULL if lSINGLY */
  828.         new->nxt = list->current;
  829.  
  830.         if (list->sd == lDOUBLY) {
  831.             ((list->current)->prv)->nxt = new;
  832.             (list->current)->prv = new;
  833.         } else {
  834.             node = list->first;
  835.                 /* search for last before current */
  836.             while (node->nxt != list->current && node != list->last)
  837.                 node = node->nxt;
  838.             node->nxt = new;
  839.         }
  840.         if (list->current == list->first)
  841.             list->first = new;
  842.         break;
  843.     case lAFTER:
  844.         if (list->sd == lDOUBLY)
  845.             new->prv = list->current;
  846.         else
  847.             new->prv = NULL;
  848.         new->nxt = (list->current)->nxt;
  849.         if (list->sd == lDOUBLY) {
  850.             ((list->current)->nxt)->prv = new;
  851.             (list->current)->prv = new;
  852.         }
  853.         (list->current)->nxt = new;
  854.         if (list->current == list->last)
  855.             list->last = new;
  856.         break;
  857.     case lLAST:
  858.         node = list->last;
  859.         if (list->sd == lDOUBLY)
  860.             new->prv = node;
  861.         else
  862.             new->prv = NULL;
  863.         if (list->cc == lCIRCULAR)
  864.             new->nxt = list->first;
  865.         else
  866.             new->nxt = NULL;
  867.         if (list->sd == lDOUBLY && list->cc == lCIRCULAR)
  868.             (list->first)->prv = new;
  869.         node->nxt = new;
  870.         list->last = new;
  871.         break;
  872.     }
  873.  
  874.     list->n++;
  875.     list->current = new;
  876.  
  877.     return(lSUCCESS);
  878. }
  879.  
  880. /*******************************************************************************
  881. ** Get info of node of linked list.
  882. **
  883. ** Parameters:
  884. **    In    int    id    identifier of linked list
  885. **    In    int    which    which node must be inspected
  886. **                (lFIRST, lPREVIOUS, lCURRENT, lNEXT, lLAST)
  887. **    Out    int    *size    size of data of node
  888. **    Out    int    *flag    user information flag
  889. **
  890. ** Return on success:
  891. **    lSUCCESS
  892. ** Return on error:
  893. **    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH, lEOL, lNOT_DOUBLY
  894. */
  895. #ifdef ANSI
  896. int
  897. lInfoNode(int id, int which, int *size, int *flag)
  898. #else
  899. int
  900. lInfoNode(id, which, size, flag)
  901. int    id, which, *size, *flag;
  902. #endif
  903. {
  904.     ListPtr    list;
  905.     int    rtrn;
  906.  
  907.     rtrn = setWhchNode(id, which, "lInfoNode");
  908.     if (rtrn != lSUCCESS)    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH, */
  909.         return(rtrn);    /* lEOL, lNOT_DOUBLY */
  910.  
  911.     list = getAddress(id);    /* already checked in setWhchNode */
  912.  
  913.         /* copy information */
  914.     *size = (list->current)->size;
  915.     *flag = (list->current)->flag;
  916.  
  917.     return(lSUCCESS);
  918. }
  919.  
  920. /*******************************************************************************
  921. ** Get data of node.
  922. **
  923. ** Parameters:
  924. **    In    int    id    identifier of linked list
  925. **    In    int    which    which node must be retrieved
  926. **                (lFIRST, lPREVIOUS, lCURRENT, lNEXT, lLAST)
  927. **    Out    Byte    *data    data of node
  928. **    In    int    size    size of data
  929. **
  930. ** Return on success:
  931. **    lSUCCESS, lFIRST, lLAST
  932. ** Return on error:
  933. **    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH, lEOL, lNOT_DOUBLY, lSIZE_NE
  934. */
  935. #ifdef ANSI
  936. int
  937. lGetNode(int id, int which, Byte *data, int size)
  938. #else
  939. int
  940. lGetNode(id, which, data, size)
  941. int    id, which, size;
  942. Byte    *data;
  943. #endif
  944. {
  945.     ListPtr    list;
  946.     int    rtrn;
  947.  
  948.     rtrn = setWhchNode(id, which, "lInfoNode");
  949.     if (rtrn != lSUCCESS)    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH, */
  950.         return(rtrn);    /* lEOL, lNOT_DOUBLY */
  951.  
  952.     list = getAddress(id);    /* already checked in setWhchNode */
  953.  
  954.         /* expected data and node must have same size */
  955.     if ((list->current)->size != size) {
  956.         lError("lGetNode", lSIZE_NE, size, (list->current)->size, NULL);
  957.         return(lSIZE_NE);
  958.     }
  959.  
  960.     BYTE_COPY((list->current)->data, data, size);
  961.  
  962.     if (list->current == list->first)
  963.         return(lFIRST);
  964.     else if (list->current == list->last)
  965.         return(lLAST);
  966.  
  967.     return(lSUCCESS);
  968. }
  969.  
  970. /*******************************************************************************
  971. ** Find node.
  972. **
  973. ** Parameters:
  974. **    In    int    id    identifier of linked list
  975. **    In    int    where    from where must be searched
  976. **    In    Func    func    function for checking the data on conditions
  977. **    In    Byte    *ptr    data for comparison in function
  978. **    Out    Byte    *data    data of node
  979. **    In    int    size    size of data
  980. **
  981. ** Return on success:
  982. **    lFOUND, lFIRST, lLAST, lNOT_FOUND
  983. ** Return on error:
  984. **    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHERE, lUNKNOWN_FUNC, lNOT_DOUBLY
  985. */
  986. #ifdef ANSI
  987. int
  988. lFndNode(int id, int where, Func func, Byte *ptr, Byte *data, int size)
  989. #else
  990. int
  991. lFndNode(id, where, func, ptr, data, size)
  992. int    id, where, size;
  993. Func    func;
  994. Byte    *ptr, *data;
  995. #endif
  996. {
  997.     NodePtr        node;
  998.     ListPtr        list;
  999.     int        cmp = lNOT_FOUND;
  1000.     static int    set[] = { lFIRST, lNEXT, lPREVIOUS, lLAST };
  1001.  
  1002.         /* check parameters */
  1003.     if ((list = getAddress(id)) == NULL) {
  1004.         lError("lFndNode", lUNKNOWN_ID, id, 0, NULL);
  1005.         return(lUNKNOWN_ID);
  1006.     }
  1007.     if (list->n == 0) {
  1008.         lError("lFndNode", lEMPTY_LIST, id, 0, NULL);
  1009.         return(lEMPTY_LIST);
  1010.     }
  1011.     if (intInSet(where, set, 4) != 0) {
  1012.         lError("lFndNode", lWRONG_WHERE, where, 0, NULL);
  1013.         return(lWRONG_WHERE);
  1014.     }
  1015.     if (func == NULL) {
  1016.         lError("lFndNode", lUNKNOWN_FUNC, (int) func, 0, NULL);
  1017.         return(lUNKNOWN_FUNC);
  1018.     }
  1019.  
  1020.         /* set node for where searching must start */
  1021.     switch (where) {
  1022.     case lFIRST:    node = list->first;    break;
  1023.     case lNEXT:
  1024.     case lPREVIOUS:    node = list->current;    break;
  1025.     case lLAST:    node = list->last;    break;
  1026.     }
  1027.  
  1028.         /* expected data and node must have same size */
  1029.     if ((where == lFIRST || where == lLAST) && node->size == size) {
  1030.         BYTE_COPY(node->data, data, size);
  1031.         cmp = (*func)(ptr, data);
  1032.     }
  1033.  
  1034.     switch (where) {
  1035.     case lFIRST:    /* search forward */
  1036.     case lNEXT:
  1037.         while (cmp != lFOUND && node->nxt != NULL
  1038.          && node != list->last) {
  1039.             node = node->nxt;
  1040.                 /* expected data and node must have same size */
  1041.             if (node->size == size) {
  1042.                 BYTE_COPY(node->data, data, size);
  1043.                 cmp = (*func)(ptr, data);
  1044.             }
  1045.         }
  1046.         if (cmp == lFOUND) {
  1047.             list->current = node;
  1048.             if (list->current == list->last)
  1049.                 return(lLAST);
  1050.         }
  1051.         break;
  1052.     case lPREVIOUS:    /* search backward */
  1053.     case lLAST:
  1054.         if (list->sd != lDOUBLY && cmp == lNOT_FOUND) {
  1055.             lError("lFndNode", lNOT_DOUBLY, id, 0, NULL);
  1056.             return(lNOT_DOUBLY);
  1057.         }
  1058.         while (cmp != lFOUND && node->prv != NULL
  1059.          && node->prv != list->first) {
  1060.             node = node->prv;
  1061.                 /* expected data and node must have same size */
  1062.             if (node->size == size) {
  1063.                 BYTE_COPY(node->data, data, size);
  1064.                 cmp = (*func)(ptr, data);
  1065.             }
  1066.         }
  1067.         if (cmp == lFOUND) {
  1068.             list->current = node;
  1069.             if (list->current == list->first)
  1070.                 return(lFIRST);
  1071.         }
  1072.         break;
  1073.     }
  1074.  
  1075.     return(cmp);    /* lFOUND, lNOT_FOUND */
  1076. }
  1077.  
  1078. /*******************************************************************************
  1079. ** Get node by flag.
  1080. **
  1081. ** Parameters:
  1082. **    In    int    id    identifier of linked list
  1083. **    In    int    flag    flag of node which must be retrieved
  1084. **    Out    Byte    *data    data of node
  1085. **    In    int    size    size of data
  1086. **
  1087. ** Return on success:
  1088. **    lFOUND, lFIRST, lLAST, lNOT_FOUND
  1089. ** Return on error:
  1090. **    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHERE, lSIZE_NE
  1091. */
  1092. #ifdef ANSI
  1093. int
  1094. lFndFlagNode(int id, int where, int flag, Byte *data, int size)
  1095. #else
  1096. int
  1097. lFndFlagNode(id, where, flag, data, size)
  1098. int    id, where, flag, size;
  1099. Byte    *data;
  1100. #endif
  1101. {
  1102.     NodePtr        node;
  1103.     ListPtr        list;
  1104.     static int    set[] = { lFIRST, lNEXT, lPREVIOUS, lLAST };
  1105.  
  1106.         /* check parameters */
  1107.     if ((list = getAddress(id)) == NULL) {
  1108.         lError("lFndFlagNode", lUNKNOWN_ID, id, 0, NULL);
  1109.         return(lUNKNOWN_ID);
  1110.     }
  1111.     if (list->n == 0) {
  1112.         lError("lFndFlagNode", lEMPTY_LIST, id, 0, NULL);
  1113.         return(lEMPTY_LIST);
  1114.     }
  1115.     if (intInSet(where, set, 4) != 0) {
  1116.         lError("lFndFlagNode", lWRONG_WHERE, where, 0, NULL);
  1117.         return(lWRONG_WHERE);
  1118.     }
  1119.  
  1120.         /* set node for where searching must start */
  1121.     switch (where) {
  1122.     case lFIRST:
  1123.         node = list->first;
  1124.         break;
  1125.     case lNEXT:
  1126.         if ((list->current)->nxt == NULL)
  1127.             return(lNOT_FOUND);    /* end of list reached */
  1128.         node = (list->current)->nxt;
  1129.         break;
  1130.     case lPREVIOUS:
  1131.         if ((list->current)->prv == NULL)
  1132.             return(lNOT_FOUND);    /* begin of list reached */
  1133.         node = (list->current)->prv;
  1134.         break;
  1135.     case lLAST:
  1136.         node = list->last;
  1137.         break;
  1138.     }
  1139.  
  1140.         /* search till begin/end of list */
  1141.     switch (where) {
  1142.     case lFIRST:    /* search forward */
  1143.     case lNEXT:
  1144.         while (node->flag != flag && node != list->last)
  1145.             node = node->nxt;
  1146.         break;
  1147.     case lPREVIOUS:    /* search backward */
  1148.     case lLAST:
  1149.         if (list->sd != lDOUBLY) {
  1150.             lError("lFndFlagNode", lNOT_DOUBLY, id, 0, NULL);
  1151.             return(lNOT_DOUBLY);
  1152.         }
  1153.         while (node->flag != flag && node != list->first)
  1154.             node = node->prv;
  1155.         break;
  1156.     }
  1157.  
  1158.     list->current = node;
  1159.  
  1160.         /* extra flag-check for last node of list */
  1161.     if ((list->current)->flag != flag) {
  1162.         lError("lFndFlagNode", lNOT_FOUND, id, 0, NULL);
  1163.         return(lNOT_FOUND);
  1164.     }
  1165.  
  1166.         /* expected data and node must have same size */
  1167.     if ((list->current)->size != size) {
  1168.         lError("lFndFlagNode", lSIZE_NE, size, (list->current)->size,
  1169.             NULL);
  1170.         return(lSIZE_NE);
  1171.     }
  1172.  
  1173.     BYTE_COPY((list->current)->data, data, size);
  1174.  
  1175.     if (list->current == list->first)
  1176.         return(lFIRST);
  1177.     else if (list->current == list->last)
  1178.         return(lLAST);
  1179.  
  1180.     return(lFOUND);
  1181. }
  1182.  
  1183. /*******************************************************************************
  1184. ** Update curent node.
  1185. **
  1186. ** Parameters:
  1187. **    In    int    id    identifier of linked list
  1188. **    In    Byte    *data    updated data of node
  1189. **    In    int    size    size of data
  1190. **    In    int    flag    updated user information flag
  1191. **
  1192. ** Return on success:
  1193. **    lSUCCESS
  1194. ** Return on error:
  1195. **    lUNKNOWN_ID, lEMPTY_LIST
  1196. */
  1197. #ifdef ANSI
  1198. int
  1199. lUpdNode(int id, Byte *data, int size, int flag)
  1200. #else
  1201. int
  1202. lUpdNode(id, data, size, flag)
  1203. int    id, size, flag;
  1204. Byte    *data;
  1205. #endif
  1206. {
  1207.     ListPtr    list;
  1208.  
  1209.         /* check parameters */
  1210.     if ((list = getAddress(id)) == NULL) {
  1211.         lError("lUpdNode", lUNKNOWN_ID, id, 0, NULL);
  1212.         return(lUNKNOWN_ID);
  1213.     }
  1214.     if (list->n == 0) {
  1215.         lError("lUpdNode", lEMPTY_LIST, id, 0, NULL);
  1216.         return(lEMPTY_LIST);
  1217.     }
  1218.  
  1219.         /* if same size, replace node by updated node */
  1220.         /* if not same size, insert updated node on current place */
  1221.     if ((list->current)->size != size) {
  1222.         FREE((list->current)->data);
  1223.         CALLOC((list->current)->data, Byte, size);
  1224.         (list->current)->size = size;
  1225.     }
  1226.     (list->current)->flag = flag;
  1227.     BYTE_COPY(data, (list->current)->data, size);
  1228.  
  1229.     return(lSUCCESS);
  1230. }
  1231.  
  1232. /*******************************************************************************
  1233. ** Delete node.
  1234. **
  1235. ** Parameters:
  1236. **    In    int    id    identifier of linked list
  1237. **    In    int    which    which node must be deleted
  1238. **                (lFIRST, lCURRENT, lLAST)
  1239. **
  1240. ** Return on success:
  1241. **    lSUCCESS
  1242. ** Return on error:
  1243. **    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH
  1244. */
  1245. #ifdef ANSI
  1246. int
  1247. lDelNode(int id, int which)
  1248. #else
  1249. int
  1250. lDelNode(id, which)
  1251. int    id, which;
  1252. #endif
  1253. {
  1254.     NodePtr        node, prv, nxt;
  1255.     ListPtr        list;
  1256.     static int    set[] = { lFIRST, lCURRENT, lLAST };
  1257.  
  1258.         /* check parameters */
  1259.     if ((list = getAddress(id)) == NULL) {
  1260.         lError("lDelNode", lUNKNOWN_ID, id, 0, NULL);
  1261.         return(lUNKNOWN_ID);
  1262.     }
  1263.     if (list->n == 0) {
  1264.         lError("lDelNode", lEMPTY_LIST, id, 0, NULL);
  1265.         return(lEMPTY_LIST);
  1266.     }
  1267.     if (intInSet(which, set, 3) != 0) {
  1268.         lError("lDelNode", lWRONG_WHICH, which, 0, NULL);
  1269.         return(lWRONG_WHICH);
  1270.     }
  1271.  
  1272.         /* specific delete cases */
  1273.     if (list->n == 1)
  1274.         which = lONE_NODE;    /* one node in linked list */
  1275.     else if (which == lCURRENT && list->first == list->current)
  1276.         which = lFIRST;        /* current is also first node */
  1277.     else if (which == lCURRENT && list->last == list->current)
  1278.         which = lLAST;        /* current is also last node */
  1279.  
  1280.     switch (which) {
  1281.     case lONE_NODE:
  1282.         node = list->first;
  1283.         list->first = list->current = list->last = NULL;
  1284.         break;
  1285.     case lFIRST:
  1286.         node = list->first;
  1287.         nxt = node->nxt;
  1288.         if (list->cc == lCIRCULAR) {
  1289.             prv = list->last;
  1290.             prv->nxt = nxt;
  1291.         } else
  1292.             prv = node->prv;    /* == NULL if lSINGLY */
  1293.         if (list->sd == lDOUBLY)
  1294.             nxt->prv = prv;
  1295.         list->first = list->current = nxt;
  1296.         break;
  1297.     case lCURRENT:
  1298.         node = list->current;
  1299.         nxt = node->nxt;
  1300.         if (list->sd == lDOUBLY) {
  1301.             prv = node->prv;
  1302.             nxt->prv = prv;
  1303.         } else {
  1304.             prv = node = list->first;
  1305.             while (node != list->current) {
  1306.                 prv = node;
  1307.                 node = node->nxt;
  1308.             }
  1309.             if (prv == node)
  1310.                 prv = list->last;
  1311.         }
  1312.         prv->nxt = nxt;
  1313.         list->current = nxt;
  1314.         break;
  1315.     case lLAST:
  1316.         node = list->last;
  1317.         if (list->sd == lDOUBLY)
  1318.             prv = node->prv;
  1319.         else {
  1320.             if (list->current != list->last)
  1321.                 prv = node = list->current;
  1322.             else
  1323.                 prv = node = list->first;
  1324.             while (node != list->last) {
  1325.                 prv = node;
  1326.                 node = node->nxt;
  1327.             }
  1328.         }
  1329.         nxt = node->nxt;
  1330.         if (list->sd == lDOUBLY && list->cc == lCIRCULAR)
  1331.             nxt->prv = prv;
  1332.         prv->nxt = nxt;
  1333.         list->last = list->current = prv;
  1334.         break;
  1335.     }
  1336.  
  1337.     FREE(node->data);
  1338.     FREE(node);
  1339.     list->n--;
  1340.  
  1341.     return(lSUCCESS);
  1342. }
  1343.  
  1344. /*******************************************************************************
  1345. ** Get information about node by index.
  1346. **
  1347. ** Parameters:
  1348. **    In    int    id    identifier of linked list
  1349. **    In    int    index    index of node which must be inspected
  1350. **    Out    int    *size    size of data of node
  1351. **    Out    int    *flag    user information flag
  1352. **
  1353. ** Return on success:
  1354. **    lSUCCESS
  1355. ** Return on error:
  1356. **    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX
  1357. */
  1358. #ifdef ANSI
  1359. int
  1360. lInfoIndxNode(int id, int index, int *size, int *flag)
  1361. #else
  1362. int
  1363. lInfoIndxNode(id, index, size, flag)
  1364. int    id, index, *size, *flag;
  1365. #endif
  1366. {
  1367.     ListPtr    list;
  1368.     int    rtrn;
  1369.  
  1370.     rtrn = setIndxNode(id, index, "lInfoIndxNode");
  1371.     if (rtrn != lSUCCESS)
  1372.         return(rtrn);    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX */
  1373.  
  1374.     list = getAddress(id);    /* already checked in setIndxNode */
  1375.  
  1376.         /* copy information */
  1377.     *size = (list->current)->size;
  1378.     *flag = (list->current)->flag;
  1379.  
  1380.     return(lSUCCESS);
  1381. }
  1382.  
  1383. /*******************************************************************************
  1384. ** Get node by index.
  1385. **
  1386. ** Parameters:
  1387. **    In    int    id    identifier of linked list
  1388. **    In    int    index    index of node which must be retrieved
  1389. **    Out    Byte    *data    data of node
  1390. **    In    int    size    size of data
  1391. **
  1392. ** Return on success:
  1393. **    lSUCCESS, lFIRST, lLAST
  1394. ** Return on error:
  1395. **    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX, lSIZE_NE
  1396. */
  1397. #ifdef ANSI
  1398. int
  1399. lGetIndxNode(int id, int index, Byte *data, int size)
  1400. #else
  1401. int
  1402. lGetIndxNode(id, index, data, size)
  1403. int    id, index, size;
  1404. Byte    *data;
  1405. #endif
  1406. {
  1407.     ListPtr    list;
  1408.     int    rtrn;
  1409.  
  1410.     rtrn = setIndxNode(id, index, "lGetIndxNode");
  1411.     if (rtrn != lSUCCESS)
  1412.         return(rtrn);    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX */
  1413.  
  1414.     list = getAddress(id);    /* already checked in setIndxNode */
  1415.  
  1416.         /* expected data and node must have same size */
  1417.     if ((list->current)->size != size) {
  1418.         lError("lGetIndxNode", lSIZE_NE, size, (list->current)->size,
  1419.             NULL);
  1420.         return(lSIZE_NE);
  1421.     }
  1422.  
  1423.     BYTE_COPY((list->current)->data, data, size);
  1424.  
  1425.     if (list->current == list->first)
  1426.         return(lFIRST);
  1427.     else if (list->current == list->last)
  1428.         return(lLAST);
  1429.  
  1430.     return(lSUCCESS);
  1431. }
  1432.  
  1433. /*******************************************************************************
  1434. ** Update node by index.
  1435. **
  1436. ** Parameters:
  1437. **    In    int    id    identifier of linked list
  1438. **    In    int    index    index of node which must be updated
  1439. **    In    Byte    *data    updated data of node
  1440. **    In    int    size    size of data
  1441. **    In    int    flag    updated user information flag
  1442. **
  1443. ** Return on success:
  1444. **    lSUCCESS
  1445. ** Return on error:
  1446. **    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX
  1447. */
  1448. #ifdef ANSI
  1449. int
  1450. lUpdIndxNode(int id, int index, Byte *data, int size, int flag)
  1451. #else
  1452. int
  1453. lUpdIndxNode(id, index, data, size, flag)
  1454. int    id, index, size, flag;
  1455. Byte    *data;
  1456. #endif
  1457. {
  1458.     ListPtr    list;
  1459.     int    rtrn;
  1460.  
  1461.     rtrn = setIndxNode(id, index, "lUpdIndxNode");
  1462.     if (rtrn != lSUCCESS)
  1463.         return(rtrn);    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX */
  1464.  
  1465.     list = getAddress(id);    /* already checked in setIndxNode */
  1466.  
  1467.         /* if same size, replace node by updated node */
  1468.         /* if not same size, insert updated node on current place */
  1469.     if ((list->current)->size != size) {
  1470.         FREE((list->current)->data);
  1471.         CALLOC((list->current)->data, Byte, size);
  1472.         (list->current)->size = size;
  1473.     }
  1474.     (list->current)->flag = flag;
  1475.     BYTE_COPY(data, (list->current)->data, size);
  1476.  
  1477.     return(lSUCCESS);
  1478. }
  1479.  
  1480. /*******************************************************************************
  1481. ** Delete node by index.
  1482. **
  1483. ** Parameters:
  1484. **    In    int    id    identifier of linked list
  1485. **    In    int    index    index of node which must be deleted
  1486. **
  1487. ** Return on success:
  1488. **    lSUCCESS
  1489. ** Return on error:
  1490. **    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX
  1491. */
  1492. #ifdef ANSI
  1493. int
  1494. lDelIndxNode(int id, int index)
  1495. #else
  1496. int
  1497. lDelIndxNode(id, index)
  1498. int    id, index;
  1499. #endif
  1500. {
  1501.     int    rtrn;
  1502.  
  1503.     rtrn = setIndxNode(id, index, "lDelIndxNode");
  1504.     if (rtrn != lSUCCESS)
  1505.         return(rtrn);    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX */
  1506.  
  1507.     return(lDelNode(id, lCURRENT));    /* lSUCCESS */
  1508. }
  1509.  
  1510. /* ---------- static local functions ---------------------------------------- */
  1511.  
  1512. /* get address of list data */
  1513. #ifdef ANSI
  1514. static ListPtr
  1515. getAddress(int id)
  1516. #else
  1517. static ListPtr
  1518. getAddress(id)
  1519. int    id;
  1520. #endif
  1521. {
  1522.     ListPtr    list;
  1523.  
  1524.     list = ld;
  1525.     while (list != NULL && list->id != id)
  1526.         list = list->nxt;
  1527.  
  1528.     if (list == NULL)
  1529.         return(NULL);    /* id not found */
  1530.  
  1531.     if (list->sd == 0 && list->cc == 0)    /* deleted linked list */
  1532.         return(NULL);    /* deleted linked list */
  1533.  
  1534.     return(list);
  1535. }
  1536.  
  1537. /* delete nodes of a linked list */
  1538. #ifdef ANSI
  1539. static void
  1540. delNodes(NodePtr node, int n)
  1541. #else
  1542. static void
  1543. delNodes(node, n)
  1544. NodePtr    node;
  1545. int    n;
  1546. #endif
  1547. {
  1548.     NodePtr    nxt;
  1549.     int    i;
  1550.  
  1551.     for (i=0; i<n; i++) {
  1552.         nxt = node->nxt;
  1553.         FREE(node->data);
  1554.         FREE(node);
  1555.         node = nxt;
  1556.     }
  1557. }
  1558.  
  1559. /* delete info about linked list */
  1560. #ifdef ANSI
  1561. static void
  1562. delListInfo(ListPtr list)
  1563. #else
  1564. static void
  1565. delListInfo(list)
  1566. ListPtr    list;
  1567. #endif
  1568. {
  1569.     ListPtr    nxt;
  1570.  
  1571.     while (list != NULL) {
  1572.         nxt = list->nxt;
  1573.         FREE(list);
  1574.         list = nxt;
  1575.     }
  1576. }
  1577.  
  1578. /* print error message in lERROR_FILE */
  1579. #ifdef ANSI
  1580. static void
  1581. lError(char *str, int code, int int1, int int2, char *str1)
  1582. #else
  1583. static void
  1584. lError(str, code, int1, int2, str1)
  1585. char    *str, *str1;
  1586. int    code, int1, int2;
  1587. #endif
  1588. {
  1589. #ifndef MSDOS
  1590.     char    mess[60];
  1591.     FILE    *fpError, *fopen();
  1592.  
  1593.     switch (code) {
  1594.     case lWRONG_SD:
  1595.         sprintf(mess, "Parameter 'sd' has wrong value : %d", int1);
  1596.         break;
  1597.     case lWRONG_CC:
  1598.         sprintf(mess, "Parameter 'cc' has wrong value : %d", int1);
  1599.         break;
  1600.     case lWRONG_WHERE:
  1601.         sprintf(mess, "Parameter 'where' has wrong value : %d", int1);
  1602.         break;
  1603.     case lWRONG_WHICH:
  1604.         sprintf(mess, "Parameter 'which' has wrong value : %d", int1);
  1605.         break;
  1606.     case lUNKNOWN_ID:
  1607.         sprintf(mess, "List id '%d' is unknown", int1);
  1608.         break;
  1609.     case lUNKNOWN_FUNC:
  1610.         sprintf(mess, "Function '%d' is unknown", int1);
  1611.         break;
  1612.     case lNO_LIST:
  1613.         sprintf(mess, "There are no lists defined");
  1614.         break;
  1615.     case lEMPTY_LIST:
  1616. #ifdef DEBUG
  1617.         sprintf(mess, "List '%d' is empty", int1);
  1618.         break;
  1619. #else
  1620.         return;
  1621. #endif
  1622.     case lEOL:
  1623. #ifdef DEBUG
  1624.         sprintf(mess, "End of list '%d' reached", int1);
  1625.         break;
  1626. #else
  1627.         return;
  1628. #endif
  1629.     case lNOT_FOUND:
  1630. #ifdef DEBUG
  1631.         sprintf(mess, "Node not found in list '%d'", int1);
  1632.         break;
  1633. #else
  1634.         return;
  1635. #endif
  1636.     case lNOT_DOUBLY:
  1637.         sprintf(mess, "List '%d' is not doubly linked", int1);
  1638.         break;
  1639.     case lSIZE_NE:
  1640.         sprintf(mess,
  1641.             "Size of expected data '%d' and node '%d' not equal",
  1642.             int1, int2);
  1643.         break;
  1644.     case lWRONG_INDEX:
  1645.         sprintf(mess, "Index '%d' out of range [1:%d]", int1, int2);
  1646.         break;
  1647.     case lOPEN_ERROR:
  1648.         sprintf(mess, "Can't open dump-file '%s'\n", str1);
  1649.         break;
  1650.     case lWRONG_ORDER:
  1651.         sprintf(mess, "Parameter 'order' has wrong value : %d", int1);
  1652.         break;
  1653.     case lWRONG_THEORY:
  1654.         sprintf(mess, "Parameter 'theory' has wrong value : %d", int1);
  1655.         break;
  1656.     }
  1657.  
  1658.     fpError = fopen(lERROR_FILE, "a");
  1659.     if (fpError == NULL) {
  1660.         fprintf(stderr, "Can't open error-file '%s'\n", lERROR_FILE);
  1661.         fprintf(stderr, "Error, '%s': %s\n", str, mess);
  1662.     } else {
  1663.         fprintf(fpError, "Error, '%s': %s\n", str, mess);
  1664.         fclose(fpError);
  1665.     }
  1666. #endif
  1667. }
  1668.  
  1669. #ifdef ANSI
  1670. static int
  1671. setWhchNode(int id, int which, char *fname)
  1672. #else
  1673. static int
  1674. setWhchNode(id, which, fname)
  1675. int    id, which;
  1676. char    *fname;
  1677. #endif
  1678. {
  1679.     ListPtr        list;
  1680.     static int    set[] = { lFIRST, lNEXT, lCURRENT, lPREVIOUS, lLAST };
  1681.  
  1682.         /* check parameters */
  1683.     if ((list = getAddress(id)) == NULL) {
  1684.         lError(fname, lUNKNOWN_ID, id, 0, NULL);
  1685.         return(lUNKNOWN_ID);
  1686.     }
  1687.     if (list->n == 0) {
  1688.         lError(fname, lEMPTY_LIST, id, 0, NULL);
  1689.         return(lEMPTY_LIST);
  1690.     }
  1691.     if (intInSet(which, set, 5) != 0) {
  1692.         lError(fname, lWRONG_WHICH, which, 0, NULL);
  1693.         return(lWRONG_WHICH);
  1694.     }
  1695.  
  1696.         /* search for requested node */
  1697.     switch (which) {
  1698.     case lFIRST:
  1699.         list->current = list->first;
  1700.         break;
  1701.     case lNEXT:
  1702.         if ((list->current)->nxt == NULL) {
  1703.             lError(fname, lEOL, id, 0, NULL);
  1704.             return(lEOL);
  1705.         }
  1706.         list->current = (list->current)->nxt;
  1707.         break;
  1708.     case lCURRENT:
  1709.         break;
  1710.     case lPREVIOUS:
  1711.         if (list->sd != lDOUBLY) {
  1712.             lError(fname, lNOT_DOUBLY, id, 0, NULL);
  1713.             return(lNOT_DOUBLY);
  1714.         }
  1715.         if ((list->current)->prv == NULL) {
  1716.             lError(fname, lEOL, id, 0, NULL);
  1717.             return(lEOL);
  1718.         }
  1719.         list->current = (list->current)->prv;
  1720.         break;
  1721.     case lLAST:
  1722.         list->current = list->last;
  1723.         break;
  1724.     }
  1725.  
  1726.     return(lSUCCESS);
  1727. }
  1728.  
  1729. #ifdef ANSI
  1730. static int
  1731. setIndxNode(int id, int index, char *fname)
  1732. #else
  1733. static int
  1734. setIndxNode(id, index, fname)
  1735. int    id, index;
  1736. char    *fname;
  1737. #endif
  1738. {
  1739.     ListPtr    list;
  1740.     int    i;
  1741.  
  1742.         /* check parameters */
  1743.     if ((list = getAddress(id)) == NULL) {
  1744.         lError(fname, lUNKNOWN_ID, id, 0, NULL);
  1745.         return(lUNKNOWN_ID);
  1746.     }
  1747.     if (list->n == 0) {
  1748.         lError(fname, lEMPTY_LIST, id, 0, NULL);
  1749.         return(lEMPTY_LIST);
  1750.     }
  1751.     if (index < 1 || list->n < index) {
  1752.         lError(fname, lWRONG_INDEX, index, list->n, NULL);
  1753.         return(lWRONG_INDEX);
  1754.     }
  1755.  
  1756.     if (index == 1)
  1757.         list->current = list->first;
  1758.     else if (index == list->n)
  1759.         list->current = list->last;
  1760.     else {
  1761.         list->current = list->first;
  1762.         for (i=1; i<index; i++)
  1763.             list->current = (list->current)->nxt;
  1764.     }
  1765.  
  1766.     return(lSUCCESS);
  1767. }
  1768.  
  1769. /* local function for QUICK sort */
  1770. #ifdef ANSI
  1771. static int
  1772. partition(NodePtr *array, int order, Func func, int lb, int ub, int *pj)
  1773. #else
  1774. static int
  1775. partition(array, order, func, lb, ub, pj)
  1776. NodePtr    *array;
  1777. int    order, lb, ub, *pj;
  1778. Func    func;
  1779. #endif
  1780. {
  1781.     int    down, up, cmp;
  1782.     NodePtr    temp, a;
  1783.  
  1784.     a = array[lb];
  1785.     up = ub;
  1786.     down = lb;
  1787.  
  1788.     while (down < up) {
  1789.         cmp = (*func)(array[down]->data, a->data);
  1790.         while (down < ub
  1791.          && ((order == lASCENDING && (cmp == l1LT2 || cmp == lSAME))
  1792.          || (order == lDESCENDING && (cmp == l2LT1 || cmp == lSAME)))) {
  1793.             down++;
  1794.             cmp = (*func)(array[down]->data, a->data);
  1795.         }
  1796.         cmp = (*func)(array[up]->data, a->data);
  1797.         while ((order == lASCENDING && cmp == l2LT1)
  1798.          || (order == lDESCENDING && cmp == l1LT2)) {
  1799.             up--;
  1800.             cmp = (*func)(array[up]->data, a->data);
  1801.         }
  1802.  
  1803.         if (down < up) {    /* interchange */
  1804.             temp = array[down];
  1805.             array[down] = array[up];
  1806.             array[up] = temp;
  1807.         }
  1808.     }
  1809.     array[lb] = array[up];
  1810.     array[up] = a;
  1811.     *pj = up;
  1812. }
  1813.  
  1814. /* local function for QUICK sort */
  1815. #ifdef ANSI
  1816. static int
  1817. stack_empty(int id)
  1818. #else
  1819. static int
  1820. stack_empty(id)
  1821. int    id;
  1822. #endif
  1823. {
  1824.     int    sd, cc, n;
  1825.  
  1826.         /* check to see if linked list exists */
  1827.     if (lInfo(id, &sd, &cc, &n) == lUNKNOWN_ID)
  1828.         return(1);    /* linked list is non-existant */
  1829.     if (n == 0)
  1830.         return(1);
  1831.     return(0);
  1832. }
  1833.  
  1834. /* ---------- static local functions (~anita/Tools/Clib) -------------------- */
  1835.  
  1836. /* check if integer belongs to set of integers */
  1837. static int
  1838. intInSet(intgr, set, set_n)
  1839. int    intgr, *set, set_n;
  1840. {
  1841.     int    i = 0;
  1842.  
  1843.     while (set[i] != intgr && i < set_n)
  1844.         i++;
  1845.  
  1846.         /* 0 = yes, 1 = no */
  1847.     return((i == set_n) ? 1 : 0);
  1848. }
  1849.